分散型階層構造クラスタ化ピアツーピア・ライブ・ストリーミング・システム

专利摘要:
送信キュー内のデータを同一クラスタ内の第１のピアに転送する処理と、平均送信キュー・サイズを算出する処理と、平均送信キュー・サイズを閾値と比較する処理と、該比較の結果に基づいて信号をクラスタ・ヘッドに送る処理と、を含む方法と装置を提供する。また、送信キュー内のデータを、上位レベルのピアに関連付けられたピアに転送する処理と、下位レベルのクラスタに関連付けられた信号キュー内の第１の信号に応答して、再生バッファ内のデータを下位レベルのクラスタ内のピアに転送する処理と、再生バッファが、一定期間の間、閾値を超えているか否かを判定する処理と、該判定の結果に基づいて第２の信号を供給元サーバに送る処理と、を含む方法と装置も提供する。
公开号:JP2011515908A
申请号:JP2010548649
申请日:2008-02-27
公开日:2011-05-19
发明作者:ガオ，ヤン；リアン，チヤオ；リウ，ヨン
申请人:トムソン ライセンシングＴｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ；
IPC主号:H04L12-863

专利说明:

[0001] 本発明は、ネットワーク通信に関し、詳しくは、ピアツーピアのネットワークに於けるデータのストリーミングに関する。]
背景技術

[0002] 先行技術では、ピアツーピア（Ｐ２Ｐ）ストリーミング・システムに於ける最大ビデオ・ストリーミング・レートは、ビデオ供給元のサーバの最大出力、当該システムに於けるピア数、及び、全ピアの総アップロード最大出力によって決まる。この最大ストリーミング・レートを実現するために、ある集中型「完全（パーフェクト）」スケジューリング・アルゴリズムが発見された。しかし、この「完全」スケジューリング・アルゴリズムには、２つの欠点がある。先ず、この「完全」スケジューリング・アルゴリズムは、個々のピア全てのアップロード最大出力情報を収集する中央スケジュラーを必要とすることである。当該中央スケジュラーは、次に、供給元から各ピアに送られるサブストリームのレートを算出する。この「完全」スケジューリング・アルゴリズムでは、当該中央スケジュラーは、単一のポイント／ユニット／デバイスである。（記号「／」は、本明細書では、同一又は類似の構成要素又は構造体の代替名称を表している。即ち、記号「／」は、本明細書で使用される表現「又は」を意味すると解することが出来る。）更に、ピアのアップロード最大出力情報は、取得できないこともあり、また、時間の経過と共に変化する。アップロード最大出力が正確でなければ、サブストリーム・レートも正しくなくなり、その結果、システム帯域幅が十分に利用されないか、或いは、サポート可能なストリーミング・レートが過大に推定されてしまうことになる。]
[0003] サーバと全ピアとの間には完全に接続されたメッシュが必要である。通常、数千ものピアを有する１つのＰ２Ｐシステムでは、１つのピアが数千ものアクティブなＰ２Ｐ接続を維持することは非現実的である。また、サーバは、ビデオ・ストリームをサブストリームに分割して、各々のピアにそれぞれ１つのサブストリームを供給する必要がある。サーバがリアルタイムで１つのビデオ・ストリームを数千ものサブストリームに分割することは、困難である。]
[0004] 本願前の出願であるＰＣＴ／ＵＳ０７／０２５６５６では、全ピアを小さな各クラスタ（集合体）に分割してクラスタ相互間で階層構造を形成する階層構造クラスタ化Ｐ２Ｐライブ・ストリーミング・システムが考案されている。該階層構造クラスタ化Ｐ２Ｐシステムでは、理論的上限値に近いストリーミング・レートが実現される。各ピアは、当該クラスタ内の少数の近隣ピアとの接続を維持するだけで良い。集中型「完全」スケジューリング方法が、個々のクラスタ内で使用される。]
[0005] 別の本願前の特許出願であるＰＣＴ／ＵＳ０７／１５２４６には、各ピアが完全に接続されたメッシュを形成する分散型の「完全」スケジューリング方法が記載されている。]
[0006] 本発明は、階層構造クラスタ化Ｐ２Ｐライブ・ストリーミング・システム用の完全分散型スケジューリング機構に向けられたものである。この分散型スケジューリング機構は、供給元サーバ及びピア・ノードに於いて実行される。該機構は、局所情報を使用し、クラスタ・レベルに於いて中央コントローラを必要としない。従って、この分散型階層構造クラスタ化Ｐ２Ｐライブ・ストリーミング・システムは、当初の「完全」スケジューリング・アルゴリズムの２つの主要な欠点を克服している。]
[0007] 本発明の階層構造クラスタ化Ｐ２Ｐストリーミング方法を、ライブ（生の）ビデオ・ストリーミングについて説明する。しかし、ビデオ、オーディオ、マルチメディア、ストリーミングのコンテンツ、ファイル等を含む（これらに限定されるものではない）任意の形態のデータをストリーミングできる。]
[0008] 送信キュー内のデータを同一クラスタ内の第１のピアに転送する処理と、平均送信キュー・サイズを算出する処理と、平均送信キュー・サイズを閾値と比較する処理と、該比較の結果に基づいて信号をクラスタ・ヘッドに送る処理と、を含む方法と装置を提供する。また、送信キュー内のデータを、上位レベルのピアに関連付けられたピアに転送する処理と、下位レベルのクラスタに関連付けられた信号キュー内の第１の信号に応答して、再生バッファ内のデータを下位レベルのクラスタ内のピアに転送する処理と、再生バッファが、一定期間の間、閾値を超えているか否かを判定する処理と、該判定の結果に基づいて第２の信号を供給元サーバに送る処理と、を含む方法と装置も提供する。更に、信号キュー内の信号に応答して、データを該信号の送出元に転送する処理と、コンテンツ・バッファ内のデータを同一クラスタ内のピアに転送する処理と、を含む方法と装置も提供する。更に、供給元サーバが更なるデータを供給できるか否かを判定する処理と、供給元サーバが更なるデータを供給できる場合に、該更なるデータをコンテンツ・バッファに移送する処理と、第１のサブサーバが第２のサブサーバよりも顕著に遅れているか否かを判定する処理と、第１のサブサーバが第２のサブサーバよりも顕著に遅れている場合、第１のサブサーバのデータ処理行程を実行する処理と、第１のサブサーバが第２のサブサーバよりも顕著に遅れていない場合、第２のサブサーバのデータ処理行程を実行する処理と、を含む方法と装置も提供する。]
図面の簡単な説明

[0009] 本発明は、添付図面を参照して以下の詳細な説明を読むことにより最良に理解できる。添付図面には以下に説明する各図が含まれており、各図に於ける同じ番号は同じ構成要素を表している。
「完全」スケジューリング・アルゴリズムを用いた先行技術のＰ２Ｐシステムの概略図である。
先行技術の階層構造クラスタ化Ｐ２Ｐストリーミング（ＨＣＰＳ）システムの概略図である。
本発明の「通常の」ピア／ノードについてのキュー・モデルを示す図である。
本発明のクラスタ・ヘッドについてのキュー・モデルを示す図である。
本発明の供給元サーバについてのキュー・モデルを示す図である。
本発明の「通常の」ピア／ノードのアーキテクチャを示す図である。
本発明の「通常の」ピア／ノードのデータ処理行程のフローチャートである。
本発明のクラスタ・ヘッドのアーキテクチャを示す図である。
本発明のクラスタ・ヘッドのデータ処理行程のフローチャートである。
本発明の供給元サーバのアーキテクチャを示す図である。
本発明のサブサーバのデータ処理行程のフローチャートである。
本発明の供給元サーバのデータ処理行程のフローチャートである。]
実施例

[0010] 先行技術方式に於いて、Ｐ２Ｐシステムによって許される最大ストリーミング・レートを実現する「完全」スケジューリング・アルゴリズムが発見された。当該システム内にｎ個のピアが存在し、ピアｉのアップロード最大出力がｕｉであり（但し、ｉ＝１、２、・・・、ｎ）、当該システム内に１個の供給元（サーバ）が存在し、そのアップロード最大出力がｕｓであり、当該システムによって許される最大ストリーミング・レートをｒｍａｘとすると、その最大ストリーミング・レートは、以下の如く表すことが出来る。



ここで、



の値は、ピア毎の平均アップロード最大出力である。]
[0011] 図１は、如何に、相異なる各データ部分が、先行技術の「完全」スケジューリング・アルゴリズムによって３個の異機種ノードの間でスケジューリングされるかを例示している。当該システムでは、３個のピア／ノードが存在している。供給元サーバは、単位時間毎に６チャンクの最大出力を有している（チャンクは基本データ単位）。ａ、ｂ及びｃのアップロード最大出力は、それぞれ、単位時間毎に２チャンク、単位時間毎に４チャンク、及び、単位時間毎に６チャンクである。仮に全てのピアが十分なダウンロード最大出力を有しているとすれば、当該システムによってサポートされ得る最大データ／ビデオ・レートは、単位時間毎に６チャンクである。このレートを実現する為には、サーバは、データ／ビデオ・チャンクを６の各グループに分割する。ノードａは、各々のグループからの１チャンクのアップロードを担当し、ノードｂ及びｃは、各々のグループ内の２チャンク及び３チャンクを担当する。これにより、全てのピアが単位毎に６チャンクの最大レートでデータ／ビデオをダウンロードできる。このような「完全」スケジューリング・アルゴリズムを実施する為には、各々のピアが、当該システム内の他の全てのピアと接続を維持してデータ／ビデオ・コンテンツを交換する必要がある。更に、サーバは、ビデオ・ストリームを多数のサブストリームに分割して、その各サブストリームが相異なるレートを有し、且つ、各々のピアに対してそれぞれ１つのサブストリームが供給されるようにする必要がある。実際の現実的なＰ２Ｐストリーミング・システムは、数千ものピアを容易に有することが出来る。現在運用されている各システムでは、１個の普通のピアが数千もの同時接続を維持することは非現実的である。また、１個のサーバが１つのデータ／ビデオ・ストリームを数千ものサブストリームにリアルタイムで分割することも困難である。] 図１
[0012] 前発明の階層構造クラスタ化Ｐ２Ｐストリーミング（ＨＣＰＳ）システムは、短い遅延で、最適な上限に近いストリーミング・レートをサポートし、しかも、実際に多数のユーザ／ピア／ノード／クライアントを収容する適応性を有している。前発明のＨＣＰＳでは、各ピアを小サイズのクラスタにグループ化し、各クラスタの間で階層構造を形成して供給元サーバからデータ／ビデオを取得している。各クラスタの間で各アップロード最大出力のバランスを能動的に取り、各々のクラスタ内に於いて「完全」スケジューリング・アルゴリズムを実行することによって、システム資源を効率的に使用できる。]
[0013] 図２には、２レベルＨＣＰＳシステムが示されている。各ピア／ノードは、帯域幅のバランスが取られた各クラスタに組織化されて、各々のクラスタは少数のピアにより構成されている。この例では、３０個のピアが均等に６個のクラスタに分けられている。各々のクラスタ内に於いて、１つのピアがクラスタ・ヘッドとして選択されている。クラスタ・ヘッドは、自己のクラスタ内の各ピアに対して、局所的なデータ／ビデオ・プロキシ・サーバとして作用する。「通常の」ピアは、当該クラスタ内で接続を維持するが、他のクラスタ内のピア／ノードとの接続を維持する必要はない。各クラスタ・ヘッドは、自己がヘッドを勤めるクラスタの各ピアとの接続を維持するのみならず、データ／ビデオを取得する上位レベルのクラスタにピアとして参加している。例えば、図２に於いて、全てのクラスタの各クラスタ・ヘッドは、２つの上位レベルのクラスタを形成して、データ／ビデオ供給元サーバからデータ／ビデオを取得する。本発明のアーキテクチャでは、供給元サーバが、データ／ビデオを各クラスタ・ヘッドと上位レベルのクラスタ内の各ピアに配信する。この２レベルＨＣＰＳの例は、サーバ、各クラスタ・ヘッド及び各通常のピアについての接続要件を最小に抑えつつ、多数のピアをサポートすることが出来る。] 図２
[0014] 同一のクラスタ内の各ピアは、「完全」スケジューリング・アルゴリズムに従って、協働して自己のクラスタ・ヘッドからデータ／ビデオを取得できるが、ＨＣＰＳに於いて使用される「完全」スケジューリングは、実際にはあまり十分に機能しない。本発明のＨＣＰＳアーキテクチャについて機能する分散型スケジューリング機構を説明する。本発明の分散型スケジューリング方法は、多数のユーザ／ピア／ノードに対応できる一方、個々のユーザ／ピア／ノードは、少数のピア／ノード接続を維持して、局所的に得られる情報に従って他のピア／ノード／ユーザとデータを交換する。]
[0015] 本発明のＨＣＰＳシステムに於いては、３つのタイプのノード／ピア、即ち、供給元サーバ、クラスタ・ヘッド、及び、「通常の（ノーマル）」ピアが存在する。供給元サーバは、システム全体の本当のサーバである。供給元サーバは、１つ又は複数のトップレベルのクラスタに対応できる。例えば、図２の供給元サーバは、２つのトップレベルのクラスタに対応できる。クラスタ・ヘッドは、２つのクラスタ、即ち、上位レベルのクラスタと下位レベルのクラスタとに参加している。クラスタ・ヘッドは、上位レベルのクラスタ内の「通常の」ピアとして作用する一方、上位レベルのクラスタからデータ／ビデオ・コンテンツを取得する。即ち、上位レベルのクラスタに於いて、クラスタ・ヘッドは、供給元サーバ／クラスタ・ヘッドからストリーミング・コンテンツを受信する、及び／又は、当該クラスタ内の他のクラスタ・ヘッド（ノード／ピア）とデータ／ストリーミング・コンテンツを交換する。次に、クラスタ・ヘッドは、下位レベルのクラスタに対する局所的な供給元として機能する。最後に、「通常の」ピアは、１つのクラスタだけに参加するピア／ノードであり、クラスタ・ヘッドからストリーミング・コンテンツを受信し、同一クラスタ内の他のピアとデータを交換する。図２に於いて、ピアａ１、ａ２、ａ３とｂ１、ｂ２、ｂ３が各クラスタ・ヘッドである。これらは、自己のそれぞれの下位レベルのクラスタ内で供給元として働く（供給元サーバのように作用する）。その間、クラスタ・ヘッドａ１、ａ２、ａ３と供給元サーバとは一方のトップレベルのクラスタを形成し、クラスタ・ヘッドｂ１、ｂ２、ｂ３と供給元サーバとは他方のトップレベルのクラスタを形成している。尚、２レベルよりも高いレベルを含むアーキテクチャも可能であるが、本明細書では本発明の原理を説明するために２レベルのアーキテクチャが使用されている。] 図２
[0016] 次に、「通常の」ピア（下位レベルに於けるもの）、クラスタ・ヘッド及び供給元サーバについての分散型スケジューリング機構、キュー・モデル、及び、アーキテクチャについて、それぞれ、説明する。]
[0017] 図３に示されているように、「通常の」ピア／ノード（下位レベルのもの）は、全ての受信ストリーミング・コンテンツを再生バッファに格納する。また、「通常の」ピア／ノードは、クラスタ内の他の全ての「通常の」ピア／ノードに転送すべきコンテンツを転送キューに格納する。供給元として働くクラスタ・ヘッドから取得されたコンテンツは、「Ｆ」或いは「ＮＦ」とマークされている。「Ｆ」は、当該コンテンツをクラスタ内の他の「通常の」ピア／ノードに中継する必要があることを表している。「ＮＦ」は、当該コンテンツがそのピア用のみであり、転送の必要がないことを意味している。他の「通常の」ピアから受信されたコンテンツは、常に「ＮＦ」コンテンツとしてマークされている。受信コンテンツは、先ず、再生バッファに保存される。「Ｆ」とマークされたコンテンツは、次に転送キューに格納され、クラスタ内の他の「通常の」ピアに転送される。転送キューが空に成ると常に、「通常の」ピアは、クラスタ・ヘッドに「プル（ｐｕｌｌ）」信号を送出して、更なるコンテンツを求める。] 図３
[0018] 図６には、「通常の」ピアのアーキテクチャが例示されている。受信行程は、クラスタ・ヘッド及び他の「通常の」ピアからの入来トラフィックを取り扱う。受信データは、次にデータ処理行程に送られる。データ処理行程には、「プル」信号送出器、パケット処理器及び再生バッファが含まれている。再生バッファに格納されたデータ・チャンクは、ユーザ（ピア／ノードに於けるユーザ）が再生バッファに格納されたストリーミング済みデータを連続プログラムとして見ることが出来るように描画される。他のノードに送信する必要があるデータ及び信号は、送信キューに格納される。送信行程は、送信キュー内のデータ及び信号の送信処理を行う。受信行程、データ処理行程及び送信行程は、各々が「通常の」ピア内で個別の行程／モジュールであっても良いし、或いは、まとめて単一の行程／モジュールであっても良い。同様に、「プル」信号を送出する行程／モジュール、データ・パケットを処理する行程／モジュール、及び、再生バッファは、まとめて単一の行程／モジュールで実施されても良いし、或いは、各々が個別の行程／モジュールで実施されても良い。これらの行程／モジュールは、プロセッサのメモリに格納された各命令を用いるソフトウェアの形態で実施しても良いし、或いは、特定用途向け集積回路（ＡＳＩＣ）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）等を用いるハードウェア又はファームウェアの形態で実施しても良い。ここに記載したキュー及びバッファは記憶装置の形態で実施しても良く、それはプロセッサの一部分であっても、或いは、別個のユニット／デバイスであっても良い。ピアツーピアの接続は、有線ネットワーク、無線ネットワーク、或いは、それらの組み合わせを通じて確立できる。] 図６
[0019] 図７は、「通常の」ピア／ノードに於ける本発明の方法を説明するフローチャートである。７０５に於いて、「通常の」ピアは、受信行程に於いてデータ・チャンクを受信する。即ち、受信行程は、クラスタ・ヘッド、及び／又は、クラスタ内の他の「通常の」ピア／ノードから入来データ・チャンクを受信する。次に７１０に於いて、データ・チャンクは、データ処理行程に送られ、データ処理行程のパケット処理器によって再生バッファに格納される。「Ｆ」とマークされたデータ・チャンクは、パケット処理器によって送信行程に送られ、送信キューに格納される。７１５に於いて、「Ｆ」とマークされたデータ・チャンクは、送信キューに於いてマーク解除されて（マークをはずされて）、同一クラスタ内の全てのピア／ノードに転送される。７２０に於いて、「プル」信号送出器は、送信キューの平均キュー・サイズを計算する。７２５に於いて、平均キュー・サイズが所定の閾値以下であるか否かを判定する検査が行われる。平均キュー・サイズが所定の閾値以下である場合に、７３０に於いて、「プル」信号送出器が、更なるコンテンツ／データを得る為に、「プル」信号を生成してクラスタ・ヘッドに送る。平均キュー・サイズが所定の閾値より大きい場合、本方法は７０５に進む。] 図７
[0020] クラスタ・ヘッドは、２つのクラスタに参加している。即ち、クラスタ・ヘッドは、同時に２つのクラスタのメンバとなる。クラスタ・ヘッドは、上位レベルのクラスタ内の「通常の」ピアとして作用し、下位レベルのクラスタ内の供給元ノードとして作用する。従って、クラスタ・ヘッドのキュー・モデルも、図４に示されているように２レベルである。クラスタ・ヘッドは、上位レベルのクラスタ内の「通常の」ノードとして、同一クラスタ内のピアからと供給元サーバからコンテンツを受信する。クラスタ・ヘッドは、同一の上位レベルのクラスタ内の他のピアに対して「Ｆ」とマークされたコンテンツを中継し、更なるコンテンツを必要とする場合は、「プル」信号を供給元サーバに送出する。上位レベルに於いて、クラスタ・ヘッドは、スロットル（ｔｈｒｏｔｔｌｅ）信号も供給元サーバに送出することがある。この点について、以下に更に詳しく説明する。] 図４
[0021] 更に図４を参照すると、クラスタ・ヘッドは、下位レベルのクラスタ内の供給元として、２つのキュー、即ち、コンテンツ・キューと信号キューを有している。該コンテンツ・キューは、２つのサーバ、即ち、「Ｆ」とマークされたコンテンツのサーバと転送サーバとを有するマルチサーバ・キューである。どちらのサーバを使用するかは、信号キューの状態によって決まる。具体的には、信号キューに「プル」信号がある場合、少数チャンクのコンテンツが、コンテンツ・バッファから取り出されて、「Ｆ」とマークされて、「Ｆ」とマークされたコンテンツのサーバによって当該「プル」信号を送出したピアに供給される。次に、当該「プル」信号は、「プル」信号キューから取り除かれる。一方、信号キューが空であると、サーバは、少数チャンクのコンテンツ（データ・チャンク）をコンテンツ・バッファから取り出して転送サーバに送る。転送サーバは、当該データ・チャンクを「ＮＦ」とマークして、それを同一クラスタ内の全てのピアに送る。] 図４
[0022] クラスタ・ヘッドのアップロード最大出力は、上位レベルのクラスタと下位レベルのクラスタとの間で分配される。ｄＨＣＰＳシステムによって許される最大ストリーミング・レートを実現する為に、下位レベルのクラスタ内の転送サーバと「Ｆ」とマークされたコンテンツのサーバとは、常に、上位レベルのクラスタ内の転送キューに対して優先権を有する。具体的には、クラスタ・ヘッドは、下位レベルのクラスタについての再生バッファ内のコンテンツが完全に対応されるまでは、上位レベルの転送キューに対応しない。]
[0023] 上位レベルのクラスタに於いてサポートされるストリーミング・レートが下位レベルのクラスタによってサポートされるストリーミング・レートより高い場合、下位レベルのクラスタは、上位レベルのクラスタによって、対応できないほどの負担を負わされることが起こり得る。クラスタ・ヘッドの全アップロード最大出力が下位レベルに於いて使用されており、しかもなお、上位レベルのコンテンツ・バッファに蓄積されたコンテンツが増え続けている場合は、現在のストリーミング・レートが高すぎて下位レベルのクラスタによってサポートされ得ないと推測できる。クラスタ・ヘッドの再生バッファにはフィードバック・メカニズムが導入されている。再生バッファは、入来ストリーミング・レートを常に推定するコンテンツ・レート推定器を有している。再生バッファには、閾値が設定されている。受信コンテンツが長期間、例えば、期間ｔに亘って、該閾値を越えている場合、クラスタ・ヘッドは、推定された入来ストリーミング・レートと共にスロットル信号を供給元サーバに送る。この信号は、現在のストリーミング・レートが、当該ノードがヘッドを勤める下位レベルのクラスタによってサポートされ得るレートを超過していることを供給元サーバに報告する。供給元サーバは、この「スロットル」信号に応答して、それ相応にストリーミング・レートを低減するように作用する。供給元サーバは、「スロットル」信号に応答してそれ相応にストリーミング・レートを低減することを選択できるように構成しても良い。別の選択肢として、供給元サーバは、現在のストリーミング・レートを低減しないことを選択しても良い。その場合、スロットル信号を送出した当該クラスタ内のピアは、フレーム・フリージングが頻繁に生じるような画質の劣化に遭遇することになる。しかし、この品質劣化が他のクラスタに波及することはない。]
[0024] 図８には、クラスタ・ヘッドのアーキテクチャが示されている。受信行程は、上位レベルのクラスタと下位レベルのクラスタの双方からの入来トラフィックを取り扱う。次に、受信データは、データ処理行程に送られる。上位レベルについてのデータ処理行程には、パケット処理器、再生バッファ及び「プル」信号送出器が含まれている。再生バッファに格納されたデータ・チャンクは、ユーザ（クラスタ・ヘッドに於けるユーザ）が再生バッファに格納されたストリーミング済みデータを連続プログラムとして見ることが出来るように描画される。下位レベルについてのデータ処理行程には、パケット処理器、「プル」信号処理器及びスロットル信号送出器が含まれている。下位レベルのクラスタについての入来信号キューは、「プル」信号を受信するだけである。他のノードに送る必要があるデータ及び信号は、送信キューに格納される。送信行程は、送信キュー内のデータの送信を取り扱う。上位レベルのクラスタのキュー内のデータ・チャンクは、上位レベルのクラスタ内の他のクラスタ・ヘッド／ピアに送信され、下位レベルの送信キュー内のデータ・チャンクは、当該クラスタ・ヘッドが供給元となる下位レベルのクラスタ内のピアに送信される。送信行程は、下位レベルのクラスタ内のトラフィックに、より高い優先権を与える。] 図８
[0025] 受信行程、データ処理行程及び送信行程は、各々がクラスタ・ヘッド内で個別の行程／モジュールであっても良いし、或いは、まとめて単一の行程／モジュールであっても良い。同様に、「プル」信号を送出する行程／モジュール、パケットを処理する行程／モジュール、及び、再生バッファは、まとめて単一の行程／モジュールで実施されても良いし、或いは、各々が個別の行程／モジュールで実施されても良い。当該行程／モジュールは、プロセッサのメモリに格納された各命令を用いるソフトウェアの形態で実施しても良いし、或いは、特定用途向け集積回路（ＡＳＩＣ）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）等を用いるハードウェア又はファームウェアの形態で実施しても良い。ここに記載したキュー及びバッファは記憶装置の形態で実施しても良く、それらは、プロセッサの一部分であっても、或いは、別個のユニット／デバイスであっても良い。]
[0026] 図９は、クラスタ・ヘッドについてのデータ処理のプロセスを説明するフローチャートである。９０５に於いて、クラスタ・ヘッドは、入来データ・チャンクを受信して（上位レベルの入来信号キュー）、その受信入来データ・チャンクを自己の再生バッファに格納する。９１０に於いて、上位レベルのデータ処理行程のパケット処理器は、送信行程の上位レベルのクラスタ内の送信キューに、「Ｆ」とマークされたデータ・チャンクを格納する。この「Ｆ」とマークされたデータ・チャンクは、他のクラスタ・ヘッド及び同一クラスタ内の各ピアに転送されるべきものである。下位レベルのデータ処理行程のパケット処理器は、９１５に於いて信号キューを検査して、待ち状態の「プル」信号がある場合、９２０に於いて「プル」信号キューからその待ち状態の「プル」信号を取り除き、その「プル」信号を送出した下位レベルのクラスタ内の「通常の」ピアにＫ個の「Ｆ」とマークされたデータ・チャンクを供給する。下位レベルのクラスタから「プル」信号を受信することは、下位レベルのクラスタのキューが空であること、或いは、平均キュー・サイズが所定の閾値より小さいことを示している。本プロセスは、ループを形成して９１５に戻る。「プル」信号キューが空である場合、９２５に於いて、再生バッファ内の次のデータ・チャンクが「ＮＦ」とマークされて、同一の下位レベルのクラスタ内の全てのピアに供給される。９３０に於いて、再生バッファが所定の長期間ｔに亘って、閾値を越えているか否かを判定する検査が行われる。再生バッファが所定の長期間ｔに亘って閾値を越えている場合、９３５に於いて、スロットル信号が生成されて供給元サーバに送られる。再生バッファが所定の長期間ｔに亘って閾値を越えていない場合、本プロセスは９０５に進む。] 図９
[0027] 次に図５を参照する。ＨＣＰＳシステム内の供給元サーバは、１つ、或いは、複数のトップレベルのクラスタに参加しても良い。供給元サーバは、トップレベルのクラスタの各々について１つのサブサーバを有している。各々のサブサーバには、２つのキュー、即ち、コンテンツ・キューと信号キューが含まれている。該コンテンツ・キューは、２つのサーバ、即ち、「Ｆ」とマークされたコンテンツのサーバと転送サーバとを有するマルチサーバ・キューである。どちらのサーバを使用するかは、信号キューの状態によって決まる。具体的には、信号キューに「プル」信号がある場合、少数チャンクのコンテンツが、コンテンツ・バッファから取り出されて、「Ｆ」とマークされ、「Ｆ」とマークされたコンテンツのサーバによって当該「プル」信号を送出したピアに供給される。「プル」信号は、これにより役割を終える（そして信号キューから取り除かれる）。一方、信号キューが空である場合、サーバは、少数チャンクのコンテンツをコンテンツ・バッファから取り出して転送サーバに送る。該転送サーバは、当該チャンクを「ＮＦ」とマークして、それを当該クラスタ内の全てのピアに送る。] 図５
[0028] 供給元サーバは、データ／ストリーミング・コンテンツを格納するオリジナルのコンテンツ・キューである。また、供給元サーバは、下位レベルの各クラスタからの「スロットル」信号、及び、自己がトップレベルのクラスタに於いて対応できる各クラスタ・ヘッドからの「スロットル」信号も取り扱う。このサーバは、各ピア／ノードからの「スロットル」信号に従って、ストリーミング・レートを調整する。このサーバのアップロード最大出力は、トップレベルの全クラスタの間で分配される。帯域幅の分配は、次の規則に従う。
・他のクラスタよりも著しく（コンテンツ・キュー・サイズに換算した閾値分）遅れているクラスタは、当該アップロード最大出力を使用する最も高い優先権を有する。
・若し、全てのコンテンツ・キューが同じ／同様のサイズであれば、各クラスタ／サブサーバはラウンド・ロビンで対応される。]
[0029] 図１０には、供給元サーバのアーキテクチャが示されている。受信行程は、トップレベルの各クラスタの各メンバからの入来「プル」信号を取り扱う。供給元サーバはスロットル信号処理器を有している。データ／ビデオ源が各サブサーバのコンテンツ・バッファに投入される。スロットル信号によって、そのようなデータ投入処理が抑制され、ストリーミング・レートが、スロットル信号によって提案されるレートに変更されることがある。各々のサブサーバについてのデータ処理行程には、パケット処理器と「プル」信号処理器が含まれている。「プル」信号に対応する際、サブサーバのコンテンツ・バッファ内のデータ・チャンクが、その「プル」信号を送出したピアについての送信キューに投入される。「プル」信号キューが空である場合、データ・チャンクが当該クラスタ内の全てのピアへの送信キューに投入される。送信行程は、各送信キュー内のデータの送信をラウンド・ロビンで処理する。受信行程、データ処理行程及び送信行程は、各々が供給元サーバ内で個別の行程／モジュールであっても良いし、或いは、まとめて単一の行程／モジュールであっても良い。同様に、「プル」信号を送出する行程／モジュール、パケットを処理する行程／モジュール、及び、再生バッファは、まとめて単一の行程／モジュールで実施されても良いし、或いは、各々が個別の行程／モジュールで実施されても良い。当該行程／モジュールは、プロセッサのメモリに格納された各命令を用いるソフトウェアの形態で実施しても良いし、或いは、特定用途向け集積回路（ＡＳＩＣ）、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）等を用いるハードウェア又はファームウェアの形態で実施しても良い。ここに記載したキュー及びバッファは記憶装置の形態で実施しても良く、それはプロセッサの一部分であっても、或いは、別個のユニット／デバイスであっても良い。] 図１０
[0030] 図１１Ａは、サブサーバのデータ処理行程を説明するフローチャートである。この実施例に於いて、サブサーバのデータ処理行程は、１１０５に於いて信号キューを検査して、待ち状態の「プル」信号がある場合、１１１０に於いて、パケット処理器が、「プル」信号キューから該待ち状態の「プル」信号を取り除き、該「プル」信号を送出したピアにＫ個の「Ｆ」とマークされたデータ・チャンクを供給する。本行程は、ループを形成して１１０５に戻る。「プル」信号キューが空である場合、１１１５に於いて、再生バッファ内の次のデータ・チャンクが、「ＮＦ」とマークされて、同一クラスタ内の全てのピアに供給される。] 図１１Ａ
[0031] 図１１Ｂは、供給元サーバのデータ処理行程を説明するフローチャートである。１１２０に於いて、供給元サーバが自己がヘッドを勤める各ピアに更なるデータを送信／対応できるか否かを判定する検査が行われる。若し可能であれば、１１２３に於いて、更なるデータが各サブサーバのコンテンツ・バッファに投入される。１１２５に於いて、前述した帯域幅分配規則に従って、顕著に遅れたサブサーバが識別される。１１３０に於いて、先ず、識別されたサブサーバが、自己のデータ処理行程を実行し、従って、更なるデータ・チャンクを送信キューに投入できる。送信行程が全ての送信キューを公平に取り扱うので、更なるデータ・チャンクを送信キューに格納する当該サブサーバは、より大きな帯域幅を使用できる。本行程は、ループを形成して１１２５に戻る。顕著に遅れたサブサーバが無い場合、本行程は、１１３５に進み、クラスタ・カウンタが初期化される。クラスタ・カウンタは０に初期化される。尚、クラスタ・カウンタは１に初期化されても良く、その場合、１１５０に於ける検査は、ｎ＋１についてのものになる。これに代わる更に別の実施例では、クラスタ・カウンタを、先ずクラスタの最高数に初期化して、減分して行くようにしても良い。カウンタの初期化と増分又は減分とは、当業者に周知のものである。１１４０に於いて、該当するサブサーバのデータ処理行程が実行される。１１４５に於いて、クラスタ・カウンタが増分され、１１５０に於いて、最後のクラスタ・ヘッドがこのサービス・ラウンドで対応されたか否かを判定する検査が行われる。最後のクラスタ・ヘッドがこのサービス・ラウンドで対応された場合、本行程は１１２０に戻る。] 図１１Ｂ
[0032] 本明細書に記載の発明は、特定のピアツーピア・オーバレイ接続形態を有するＰ２Ｐシステムによって許される最大／最適ストリーミング・レートを実現できる。一定ビット・レート（ＣＢＲ）のビデオがそのようなＰ２Ｐシステムを通じてストリーミングされる場合、その一定ビット・レートがサポート可能最大ストリーミング・レートよりも低い限り、全てのピア／ユーザをサポートできる。]
[0033] 本明細書に記載の発明は、基礎を成すネットワークの接続形態（トポロジ）の情報を前提としておらず、また、専用ネットワーク・インフラストラクチャ、例えばネットワーク内キャッシュ・プロキシやＣＤＮ（コンテンツ配信ネットワーク）エッジ・サーバ等のサポートを前提としていない。若しそのような情報とインフラストラクチャのサポートを得られるのであれば、本発明の分散型ＨＣＰＳ（ｄＨＣＰＳ）は、それらを有効に利用して、より優れたユーザの体感品質（ＱｏＥ）を提供できる。例えば、ネットワーク接続形態が判れば、ｄＨＣＰＳは、相互に隣接した各ピアを同一クラスタにグループ化して、基礎を成すネットワーク上のトラフィック負荷を軽減して伝搬遅延を短縮できる。別の例としては、ネットワーク内キャッシュ・プロキシやＣＤＮエッジ・サーバを使用してライブの（生の）ストリーミングをサポートできるのであれば、ｄＨＣＰＳは、それらをクラスタ・ヘッドとして使用できる。その理由は、この専用ネットワーク・インフラストラクチャは、一般的に、そのアップロード最大出力が比較的大きく、且つ、ネットワークを突然に放置する可能性が比較的少ないからである。]
[0034] 本発明は、ハードウェア（例えば、ＡＳＩＣチップ）、ソフトウェア、ファームウェア、特定用途プロセッサ、或いは、それらの組み合わせの様々な形態で実施できる。本原理の各開示事項は、ハードウェアとソフトウェアとの組み合わせとして、例えば、サーバ、中間デバイス（例えば、無線アクセス・ポイント、無線ルータ、セット・トップ・ボックス、モバイル・デバイス）に於いて、実施できる。本発明は、ハードウェアとソフトウェアとの組み合わせとして実施するのが望ましい。更に、該ソフトウェアは、プログラム記憶装置に実装されたアプリケーション・プログラムとして実施するのが望ましい。該アプリケーション・プログラムは、任意の適切なアーキテクチャから成るマシンにアップロードして、該マシンにより実行できる。該マシンは、１つ以上の中央処理装置（ＣＰＵ）、ランダム・アクセス・メモリ（ＲＡＭ）、及び、入力／出力（Ｉ／Ｏ）インタフェース等のハードウェアを有するコンピュータ・プラットフォームで実施するのが望ましい。該コンピュータ・プラットフォームには、オペレーティング・システムとマイクロインストラクション・コードも含まれている。本明細書に記載された種々の処理と機能は、オペレーティング・システムを介して実行されるマイクロインストラクション・コードの一部、或いは、アプリケーション・プログラムの一部（或いは、それらの組み合わせ）であっても良い。更に、例えば、増設データ記憶装置、及び、印刷装置等の種々のその他の周辺装置をコンピュータ・プラットフォームに接続しても良い。]
[0035] 更に、添付図面に示された各構成システム・コンポーネント及び方法の行程の一部はソフトウェアの形態で実施されることが望ましいため、システム・コンポーネント相互間（或いは、処理行程相互間）の実際の接続は、本発明がプログラムされる態様に従って、異なることがある。本明細書に記載された各開示事項により、当業者であれば、本発明のそのような、及び、同様な実施形態、或いは、コンフィギュレーション（環境設定、機器構成等）を考案できるであろう。]

权利要求:

請求項1
送信キュー内のデータを同一クラスタ内の第１のピアに転送するステップと、平均送信キュー・サイズを算出するステップと、前記平均送信キュー・サイズを閾値と比較するステップと、前記比較の結果に基づいて信号をクラスタ・ヘッドに送るステップと、を含む、方法。
請求項2
請求項１記載の方法であって、前記データを受信するステップと、前記送信キュー内に送るべき前記受信データを格納するステップと、を更に含み、前記受信データが前記クラスタ・ヘッドと前記同一クラスタ内の第２のピアの一方から受信されるものである、前記方法。
請求項3
請求項１記載の方法であって、前記受信データを再生バッファに格納するステップと、前記再生バッファ内に格納された前記データを描画するステップと、を更に含む、前記方法。
請求項4
請求項１記載の方法であって、前記信号が、前記送信キューに更なるデータが必要であることを示すものである、前記方法。
請求項5
送信キュー内のデータを同一クラスタ内の第１のピアに転送する手段と、平均送信キュー・サイズを算出する手段と、前記平均送信キュー・サイズを所定の閾値と比較する手段と、前記比較手段の結果に基づいて信号をクラスタ・ヘッドに送る手段と、を含む、装置。
請求項6
請求項５記載の装置であって、前記データを受信する手段と、前記送信キュー内に送るべき前記受信データを格納する手段と、を更に含み、前記受信データが前記クラスタ・ヘッドと前記同一クラスタ内の第２のピアの一方から受信されるものである、前記装置。
請求項7
請求項５記載の装置であって、前記受信データを再生バッファに格納する手段と、前記再生バッファ内に格納された前記データを描画する手段と、を更に含む、前記装置。
請求項8
請求項５記載の装置であって、前記信号が、前記送信キューに更なるデータが必要であることを示すものである、前記装置。
請求項9
送信キュー内のデータを、上位レベルのクラスタに関連付けられたピアに転送するステップと、下位レベルのクラスタに関連付けられた信号キュー内の第１の信号に応答して、再生バッファ内のデータを前記下位レベルのクラスタ内のピアに転送するステップと、前記再生バッファが、一定期間の間、閾値を超えているか否かを判定するステップと、前記判定するステップの結果に基づいて第２の信号を供給元サーバに送るステップと、を含む、方法。
請求項10
請求項９記載の方法であって、データを受信するステップと、前記受信データを前記再生バッファに格納するステップと、前記再生バッファに格納された前記受信データを描画するステップと、を更に含む、前記方法。
請求項11
請求項９記載の方法であって、前記受信データが、同一の上位レベルのクラスタ内の第２のクラスタ・ヘッドと前記供給元サーバの一方から受信されるものである、前記方法。
請求項12
請求項９記載の方法であって、前記第１の信号が、更なるデータが必要とされることを示すものである、前記方法。
請求項13
請求項９記載の方法であって、前記第２の信号が、データが転送されている第１のレートが、データが使用され得る第２のレートを超えていることを示すものである、前記方法。
請求項14
送信キュー内のデータを、上位レベルのクラスタに関連付けられたピアに転送する手段と、下位レベルのクラスタに関連付けられた信号キュー内の第１の信号に応答して、再生バッファ内のデータを前記下位レベルのクラスタ内のピアに転送する手段と、前記再生バッファが、一定期間の間、閾値を超えているか否かを判定する手段と、前記判定する手段の結果に基づいて第２の信号を供給元サーバに送る手段と、を含む、装置。
請求項15
請求項１４記載の装置であって、データを受信する手段と、前記受信データを前記再生バッファに格納する手段と、前記再生バッファに格納された前記受信データを描画する手段と、を更に含む、前記装置。
請求項16
請求項１４記載の装置であって、前記受信データが、前記同一の上位レベルのクラスタ内の第２のクラスタ・ヘッドと前記供給元サーバの一方から受信されるものである、前記装置。
請求項17
請求項１４記載の装置であって、前記第１の信号が、更なるデータが必要とされることを示すものである、前記装置。
請求項18
請求項１４記載の装置であって、前記第２の信号が、データが転送されている第１のレートが、データが使用され得る第２のレートを超えていることを示すものである、前記装置。
請求項19
信号キュー内の信号に応答して、データを前記信号の送出元に転送するステップと、コンテンツ・バッファ内のデータを同一クラスタ内のピアに転送するステップと、を含む、方法。
請求項20
信号キュー内の信号に応答して、データを前記信号の送出元に転送する手段と、コンテンツ・バッファ内のデータを同一クラスタ内のピアに転送する手段と、を含む、装置。
請求項21
供給元サーバが更なるデータを供給できるか否かを判定するステップと、前記供給元サーバが更なるデータを供給できる場合に、前記更なるデータをコンテンツ・バッファに移送するステップと、第１のサブサーバが第２のサブサーバよりも顕著に遅れているか否かを判定するステップと、前記第１のサブサーバが前記第２のサブサーバよりも顕著に遅れている場合、前記第１のサブサーバのデータ処理行程を実行するステップと、前記第１のサブサーバが前記第２のサブサーバよりも顕著に遅れていない場合、前記第２のサブサーバのデータ処理行程を実行するステップと、を含む、方法。
請求項22
供給元サーバが更なるデータを供給できるか否かを判定する手段と、前記供給元サーバが更なるデータを供給できる場合に、前記更なるデータをコンテンツ・バッファに移送する手段と、第１のサブサーバが第２のサブサーバよりも顕著に遅れているか否かを判定する手段と、前記第１のサブサーバが前記第２のサブサーバよりも顕著に遅れている場合、前記第１のサブサーバのデータ処理行程を実行する手段と、前記第１のサブサーバが前記第２のサブサーバよりも顕著に遅れていない場合、前記第２のサブサーバのデータ処理行程を実行する手段と、を含む、装置。